Skip to main content

Binary Search

A comprehensive guide to binary search algorithms and techniques for Data Structures and Algorithms.

Table of Contents​

  1. Basic Binary Search
  2. Template Patterns
  3. Search in Modified Arrays
  4. Finding Boundaries
  5. Peak Finding
  6. Search in 2D Arrays
  7. Answer Search (Binary Search on Answer)
  8. Advanced Applications
  9. Common Pitfalls and Tips

Binary search is a divide-and-conquer algorithm that searches for a target value in a sorted array by repeatedly dividing the search interval in half.

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

Time Complexity: O(log n) | Space Complexity: O(1)

function binarySearchRecursive(nums, target, left = 0, right = nums.length - 1) {
    if (left > right) return -1;

    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
        return mid;
    } else if (nums[mid] < target) {
        return binarySearchRecursive(nums, target, mid + 1, right);
    } else {
        return binarySearchRecursive(nums, target, left, mid - 1);
    }
}

Time Complexity: O(log n) | Space Complexity: O(log n) due to recursion stack

3. Insert Position​

Find the index where target should be inserted to maintain sorted order:

function searchInsert(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

💡 Pro Tip: Notice we use right = nums.length and left < right for insertion problems!

Template Patterns​

Understanding different binary search templates helps solve various problem types.

Use when: Direct target comparison Condition: left <= right Mid Calculation: Math.floor((left + right) / 2)

function template1(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Template 2: Find Left Boundary​

Use when: Finding first occurrence or left boundary Condition: left < right

function template2(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

Template 3: Find Right Boundary​

Use when: Finding last occurrence or right boundary Condition: left < right

function template3(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.ceil((left + right) / 2);

        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }

    return left;
}

🔧 Technique: Notice we use Math.ceil for right boundary to avoid infinite loops!

Search in Modified Arrays​

1. Search in Rotated Sorted Array​

function searchRotated(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        // Check which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

2. Search in Rotated Array II (with Duplicates)​

function searchRotatedII(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return true;
        }

        // Handle duplicates
        if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
            left++;
            right--;
        } else if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return false;
}

3. Find Minimum in Rotated Array​

function findMin(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] > nums[right]) {
            // Minimum is in right half
            left = mid + 1;
        } else {
            // Minimum is in left half (including mid)
            right = mid;
        }
    }

    return nums[left];
}

4. Find Peak Element​

function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] < nums[mid + 1]) {
            // Peak is on the right
            left = mid + 1;
        } else {
            // Peak is on the left (including mid)
            right = mid;
        }
    }

    return left;
}

Finding Boundaries​

1. First and Last Position​

function searchRange(nums, target) {
    const findFirst = () => {
        let left = 0;
        let right = nums.length;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    };

    const findLast = () => {
        let left = 0;
        let right = nums.length;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left - 1;
    };

    const first = findFirst();

    if (first >= nums.length || nums[first] !== target) {
        return [-1, -1];
    }

    return [first, findLast()];
}

2. Count Occurrences​

function countOccurrences(nums, target) {
    const [first, last] = searchRange(nums, target);

    if (first === -1) return 0;

    return last - first + 1;
}

3. Find Floor and Ceiling​

function findFloor(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let floor = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] <= target) {
            floor = nums[mid];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return floor;
}

function findCeiling(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let ceiling = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] >= target) {
            ceiling = nums[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return ceiling;
}

Peak Finding​

1. Single Peak in 1D Array​

function findSinglePeak(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        // Check if mid is a peak
        const leftVal = mid > 0 ? nums[mid - 1] : -Infinity;
        const rightVal = mid < nums.length - 1 ? nums[mid + 1] : -Infinity;

        if (nums[mid] >= leftVal && nums[mid] >= rightVal) {
            return mid;
        }

        // Move towards the higher side
        if (leftVal > nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

2. Peak in Mountain Array​

function peakIndexInMountainArray(arr) {
    let left = 1;
    let right = arr.length - 2;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
            return mid;
        }

        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Search in 2D Arrays​

1. Search in Row-wise and Column-wise Sorted Matrix​

function searchMatrix(matrix, target) {
    if (!matrix || matrix.length === 0) return false;

    let row = 0;
    let col = matrix[0].length - 1;

    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }

    return false;
}

Time Complexity: O(m + n)

2. Search in Row-sorted Matrix​

function searchMatrixRowSorted(matrix, target) {
    if (!matrix || matrix.length === 0) return false;

    const m = matrix.length;
    const n = matrix[0].length;

    let left = 0;
    let right = m * n - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midVal = matrix[Math.floor(mid / n)][mid % n];

        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

Time Complexity: O(log(m * n))

3. Find Kth Smallest in Sorted Matrix​

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let left = matrix[0][0];
    let right = matrix[n - 1][n - 1];

    const countLessEqual = (mid) => {
        let count = 0;
        let j = n - 1;

        for (let i = 0; i < n; i++) {
            while (j >= 0 && matrix[i][j] > mid) {
                j--;
            }
            count += (j + 1);
        }

        return count;
    };

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (countLessEqual(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

Binary Search on Answer Space​

This powerful technique searches for an answer within a range rather than searching within an array. We use binary search to minimize or maximize some value that meets a condition (predicate).

Key Insight: Instead of searching within an array, we are searching for an answer within a range.

This is especially useful for problems like:

  • Minimum days to complete tasks
  • Maximum/minimum capacity (e.g., boats, weights)
  • Scheduling problems
  • Optimization problems with monotonic properties

General Pattern​

function binarySearchSpace(low, high, condition) {
    let answer = -1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (condition(mid)) {
            answer = mid;
            high = mid - 1; // Try for a smaller valid value
        } else {
            low = mid + 1; // Need a bigger value
        }
    }

    return answer;
}

Pattern 1: Minimize Answer (Find First True)​

Goal: Find the minimum value that satisfies a condition. Test Case Pattern: F F F T T T

Template for Minimization​

const binarySearchFirstTrue = (minPossible, maxPossible, isValid) => {
    let left = minPossible;
    let right = maxPossible;
    let answer = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (isValid(mid)) {
            answer = mid;        // Record candidate
            right = mid - 1;     // Try smaller value
        } else {
            left = mid + 1;      // Go larger
        }
    }

    return answer;
};

Setup for Minimization:​

  • low = smallest possible value of the answer
  • high = largest possible value of the answer
  • Return: low (because loop ends when low == smallest valid)

1. Koko Eating Bananas​

function minEatingSpeed(piles, h) {
    const canFinish = (speed) => {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / speed);
        }
        return hours <= h;
    };

    let left = 1; // Minimum possible speed
    let right = Math.max(...piles); // Maximum possible speed

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (canFinish(mid)) {
            right = mid; // Try smaller speed
        } else {
            left = mid + 1; // Need faster speed
        }
    }

    return left;
}

2. Capacity to Ship Packages​

function shipWithinDays(weights, days) {
    const canShip = (capacity) => {
        let daysNeeded = 1;
        let currentWeight = 0;

        for (const weight of weights) {
            if (currentWeight + weight > capacity) {
                daysNeeded++;
                currentWeight = weight;
            } else {
                currentWeight += weight;
            }
        }

        return daysNeeded <= days;
    };

    let left = Math.max(...weights); // Must carry heaviest item
    let right = weights.reduce((sum, weight) => sum + weight, 0); // Carry all at once

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (canShip(mid)) {
            right = mid; // Try smaller capacity
        } else {
            left = mid + 1; // Need larger capacity
        }
    }

    return left;
}

3. Minimum Days to Make Bouquets​

function minDays(bloomDay, m, k) {
    const canMakeBouquets = (day) => {
        let bouquets = 0;
        let consecutive = 0;

        for (const bloom of bloomDay) {
            if (bloom <= day) {
                consecutive++;
                if (consecutive === k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }

        return bouquets >= m;
    };

    if (m * k > bloomDay.length) return -1;

    let left = Math.min(...bloomDay);
    let right = Math.max(...bloomDay);

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (canMakeBouquets(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

Pattern 2: Maximize Answer (Find Last True)​

Goal: Find the maximum value that still satisfies the condition. Test Case Pattern: T T T F F F

Template for Maximization​

const binarySearchLastTrue = (minPossible, maxPossible, isValid) => {
    let left = minPossible;
    let right = maxPossible;
    let answer = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (isValid(mid)) {
            answer = mid;       // Record candidate
            left = mid + 1;     // Try larger value
        } else {
            right = mid - 1;    // Go smaller
        }
    }

    return answer;
};

Setup for Maximization:​

  • low = smallest possible value
  • high = largest possible value
  • Return: high (last value that passed)

1. Magnetic Force Between Balls​

function maxDistance(position, m) {
    position.sort((a, b) => a - b);

    const canPlace = (minDist) => {
        let count = 1;
        let lastPos = position[0];

        for (let i = 1; i < position.length; i++) {
            if (position[i] - lastPos >= minDist) {
                count++;
                lastPos = position[i];
                if (count >= m) return true;
            }
        }

        return false;
    };

    let left = 1; // Minimum possible distance
    let right = position[position.length - 1] - position[0]; // Maximum possible distance
    let answer = 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (canPlace(mid)) {
            answer = mid;
            left = mid + 1; // Try larger distance
        } else {
            right = mid - 1; // Reduce distance
        }
    }

    return answer;
}

2. Aggressive Cows (Classic Problem)​

function aggressiveCows(stalls, cows) {
    stalls.sort((a, b) => a - b);

    const canPlaceCows = (minDist) => {
        let count = 1;
        let lastPos = stalls[0];

        for (let i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPos >= minDist) {
                count++;
                lastPos = stalls[i];
                if (count >= cows) return true;
            }
        }

        return false;
    };

    let left = 1;
    let right = stalls[stalls.length - 1] - stalls[0];
    let answer = 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (canPlaceCows(mid)) {
            answer = mid;
            left = mid + 1; // Try larger distance
        } else {
            right = mid - 1;
        }
    }

    return answer;
}

For problems requiring decimal/floating-point answers:

function precisionBinarySearch(low, high, condition, precision = 1e-6) {
    while (high - low > precision) {
        const mid = (low + high) / 2;

        if (condition(mid)) {
            low = mid; // For maximize
            // high = mid; // For minimize
        } else {
            high = mid; // For maximize
            // low = mid; // For minimize
        }
    }

    return (low + high) / 2;
}

Square Root with Precision​

function sqrtPrecision(x, precision = 1e-6) {
    if (x === 0) return 0;

    let low = 0;
    let high = x > 1 ? x : 1;

    while (high - low > precision) {
        const mid = (low + high) / 2;

        if (mid * mid <= x) {
            low = mid;
        } else {
            high = mid;
        }
    }

    return (low + high) / 2;
}

3. Split Array - Largest Sum​

function splitArray(nums, m) {
    const canSplit = (maxSum) => {
        let splits = 1;
        let currentSum = 0;

        for (const num of nums) {
            if (currentSum + num > maxSum) {
                splits++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }

        return splits <= m;
    };

    let left = Math.max(...nums);
    let right = nums.reduce((sum, num) => sum + num, 0);

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (canSplit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

Summary Table​

GoalSearch ForIf Condition PassesReturn
MinimizeFirst T in F F T T Tright = mid - 1low
MaximizeLast T in T T T F Fleft = mid + 1high
TypeUse When...Exit ConditionReturn
IntegerAnswer is a whole numberleft <= rightlow or high
PrecisionAnswer is decimal/floating-pointhigh - low > precision(low + high) / 2

How to Decide?​

SituationUse This
Answer is in integer rangeInteger binary search
Answer is fractional/decimalPrecision-based binary search
You need answers with 3-6 decimal placesPrecision search with 1e-6

Common Problems by Pattern​

Pattern 1 - Minimize (Find First True):​

ProblemDescriptionLink
🍌 Koko Eating BananasMin eating speedLeetCode 875
📦 Capacity to Ship PackagesMin ship capacityLeetCode 1011
🌸 Minimum Days to Make BouquetsMin days for bouquetsLeetCode 1482
🔢 Split Array Largest SumMin largest sumLeetCode 410
🪙 Ugly Number IIINth ugly numberLeetCode 1201

Pattern 2 - Maximize (Find Last True):​

ProblemDescriptionLink
🐄 Aggressive CowsMax min distance between cowsGFG
🧲 Magnetic Force Between BallsMax min distance between ballsLeetCode 1552
🍫 Divide ChocolateMax min sweetnessLeetCode 1231
📶 Maximum Average Subarray IIMax average with length ≥ kLeetCode 644

Precision-Based Problems:​

ProblemDescriptionLink
📊 Square Root with PrecisionFind √x to given precisionClassic
🧪 Cube Root with PrecisionFind ∛x to given precisionClassic
⚡ Water Tank FillingMin time to fill tankPractice

Advanced Applications​

1. Find Duplicate Number​

Floyd's Algorithm variant with Binary Search:

function findDuplicate(nums) {
    let left = 1;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        // Count numbers <= mid
        let count = 0;
        for (const num of nums) {
            if (num <= mid) count++;
        }

        if (count <= mid) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

2. H-Index II​

function hIndex(citations) {
    const n = citations.length;
    let left = 0;
    let right = n - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (citations[mid] >= n - mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return n - left;
}
function maxEnvelopes(envelopes) {
    // Sort by width ascending, height descending
    envelopes.sort((a, b) => a[0] - b[0] || b[1] - a[1]);

    const heights = envelopes.map(env => env[1]);

    // Find LIS of heights using binary search
    const tails = [];

    for (const height of heights) {
        let left = 0;
        let right = tails.length;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);

            if (tails[mid] < height) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        if (left === tails.length) {
            tails.push(height);
        } else {
            tails[left] = height;
        }
    }

    return tails.length;
}

4. Median of Two Sorted Arrays​

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    const m = nums1.length;
    const n = nums2.length;

    let left = 0;
    let right = m;

    while (left <= right) {
        const partitionX = Math.floor((left + right) / 2);
        const partitionY = Math.floor((m + n + 1) / 2) - partitionX;

        const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        const minRightX = partitionX === m ? Infinity : nums1[partitionX];

        const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        const minRightY = partitionY === n ? Infinity : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            right = partitionX - 1;
        } else {
            left = partitionX + 1;
        }
    }
}

Common Pitfalls and Tips​

1. Integer Overflow Prevention​

// ❌ Wrong: May cause overflow
const mid = Math.floor((left + right) / 2);

// ✅ Correct: Prevents overflow
const mid = left + Math.floor((right - left) / 2);

2. Loop Termination Conditions​

// Template choice affects termination
// left <= right: Use when returning specific index
// left < right: Use when finding boundaries or insertion points

3. Mid Calculation for Right Boundary​

// For right boundary search, use ceiling to avoid infinite loops
const mid = Math.ceil((left + right) / 2);

4. Helper Functions for Complex Problems​

function binarySearchWithHelper(nums, target) {
    const isValid = (mid) => {
        // Custom validation logic
        return /* some condition */;
    };

    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (isValid(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

Time Complexity Summary​

OperationTime ComplexitySpace Complexity
Basic Binary SearchO(log n)O(1)
Search in Rotated ArrayO(log n)O(1)
Find BoundariesO(log n)O(1)
Peak FindingO(log n)O(1)
2D Matrix SearchO(log(m*n))O(1)
Binary Search on AnswerO(log(range) * validation)O(1)
Median of Two ArraysO(log(min(m,n)))O(1)

Pattern Recognition Guide​

  1. Sorted Array: Classic binary search scenarios
  2. Search Space with Order: Even if not explicitly sorted, if you can determine direction
  3. Optimization Problems: Find minimum/maximum with monotonic property
  4. Decision Problems: Can you solve it? → Find optimal solution

Key Questions to Ask:​

  1. Is the search space monotonic?
  2. Can I eliminate half the search space at each step?
  3. What's my invariant condition?
  4. Do I need exact match or boundary?

Template Selection:​

  • Template 1: Direct target finding
  • Template 2: Left boundary, insertion point
  • Template 3: Right boundary, last occurrence

🧠 Remember: Binary search isn't just for sorted arrays - it's for any problem where you can eliminate half the search space!

Practice Problems by Category​

Beginner:​

  • Binary Search
  • Search Insert Position
  • First Bad Version
  • Valid Perfect Square

Intermediate:​

  • Search in Rotated Array
  • Find Peak Element
  • Search Range
  • H-Index II

Advanced:​

  • Median of Two Sorted Arrays
  • Split Array Largest Sum
  • Capacity to Ship Packages
  • Russian Doll Envelopes

This comprehensive guide covers all essential binary search patterns and techniques for coding interviews and competitive programming!